高考申論題
109年
[資訊處理] 資料結構
第 一 題
📖 題組：
三、請回答下列關於AVL樹（AVL Tree）的問題：
三、請回答下列關於AVL樹（AVL Tree）的問題：
我們欲將所管理的鍵值（Key）依序列出，請問是否可以利用一個AVL樹對鍵值來進行排序（Sorting）？若不行，請說明原因；如果可以，請描述方法及時間複雜度。（5分）
📝 此題為申論題
思路引導 VIP
看到 AVL 樹排序，聯想到它本質上是高度平衡的「二元搜尋樹 (BST)」。BST 的特性是對其進行中序追蹤(Inorder Traversal)就會得到排序序列。分析時間複雜度需包含兩階段：建樹 + 走訪。
🤖
AI 詳解
AI 專屬家教
【考點分析】 AVL 樹的資料結構特性、二元搜尋樹（BST）的中序追蹤（Inorder Traversal）、排序演算法時間複雜度。 【理論/法規依據】
▼ 還有更多解析內容
AVL 樹排序原理
💡 利用平衡二元樹之性質與中序追蹤，實現 O(n log n) 排序。
🔗 AVL 樹排序三步驟
- 1 逐一插入建樹 — 將 n 個鍵值插入並保持平衡，耗時 O(n log n)。
- 2 執行中序追蹤 — 依「左子樹-根-右子樹」順序走訪，耗時 O(n)。
- 3 輸出有序序列 — 根據 BST 性質，中序輸出即為遞增排序結果。
↓
↓
🔄 延伸學習：延伸學習：AVL 樹插入時的 LL, RR, LR, RL 四種旋轉平衡機制。
